<?php
/**
 * SudokuMatrix.php
 * @abstract Sudoku game matrix class
 * @author Manel Zaera (manelzaera@gmail.com)
 * @license http://www.gnu.org/copyleft/gpl.html GNU GPL
 *
 * Changes:
 * 2008-01-05, Manel Zaera (manelzaera@gmail.com), First version
 * 2008-01-10, Manel Zaera (manelzaera@gmail.com), Solve problem on calculating
 * 				square row and column offset, return valid values for a cell
 */
class SudokuMatrix {
	/** Sudoku Matrix sum ((1+2+3+4+5+6+7+8+9)*9) */
	const SUDOKU_MATRIX_SUM = 405;
	// Difficult levels
	/** Easy level */
	const LEVEL_EASY = 0;
	/** Mediuem level */
	const LEVEL_MEDIUM = 1;
	/** Hard level */
	const LEVEL_HARD = 2;
	/** Expert level */
	const LEVEL_EXPERT = 3;
	// Max. hidden cell values related to level
	/** Max. hidden cells in easy level */
	const MAX_HIDDEN_EASY = 25;
	/** Max. hidden cells in mediuem level */
	const MAX_HIDDEN_MEDIUM = 45;
	/** Max. hidden cells in hard level */
	const MAX_HIDDEN_HARD = 85;
	/** Max. hidden cells in expert level */
	const MAX_HIDDEN_EXPERT = 95;
	/* Max. hidden cells for level */
	private $aMaxHidden = array(self::LEVEL_EASY=>self::MAX_HIDDEN_EASY,
								self::LEVEL_MEDIUM=>self::MAX_HIDDEN_MEDIUM,
								self::LEVEL_HARD=>self::MAX_HIDDEN_HARD,
								self::LEVEL_EXPERT=>self::MAX_HIDDEN_EXPERT);
	// Seed to generate matrix values
	private $aSeed = array(1,2,3,4,5,6,7,8,9,
							  4,5,6,7,8,9,1,2,3,
							  7,8,9,1,2,3,4,5,6,
							  2,3,4,5,6,7,8,9,1,
							  5,6,7,8,9,1,2,3,4,
							  8,9,1,2,3,4,5,6,7,
							  3,4,5,6,7,8,9,1,2,
							  6,7,8,9,1,2,3,4,5,
							  9,1,2,3,4,5,6,7,8);
	// Present matrix values
	private $aValues = array(0,0,0,0,0,0,0,0,8,
							  0,0,0,1,0,4,0,0,0,
							  0,5,0,0,8,0,0,0,0,
							  0,0,0,0,5,0,0,9,0,
							  0,0,9,0,0,7,1,4,3,
							  8,0,0,0,0,0,6,0,0,
							  2,0,7,0,0,1,5,0,0,
							  0,3,0,0,0,0,0,0,0,
							  4,0,0,0,0,3,0,0,7);

	/**
	 * SudokuMatrix object constructor
	 * @param $iLevel Sets the difficult level (see LEVEL_* constants)
	 * @param $aInitValues Init values for Sudoku (if null then autogenerate values)
	 */
	public function __construct ($iLevel,$aInitValues=null) {
		if ($aInitValues!=null) {
			if (!$this->init($aInitValues)) {
				throw new Exception("Wrong init value");
			}
		} else {
			$this->generateValues();
			$this->hideValues($iLevel);
		}
	}

	/**
	 * Set a cell value
	 * @param $iRow Row number
	 * @param $iCol Column number
	 * @param $iValue Value to set
	 *
	 * @return bool true if cell value is valid, false otherwise
	 */
	public function checkCell($iRow,$iCol,$iValue) {
		$aOriginalValues = $this->aValues;
		$zOk = $this->setCell($iRow,$iCol,$iValue);
		$this->aValues = $aOriginalValues;
		return $zOk;
	}

	/**
	 * Check the Sudoku Matrix
	 *
	 * @return bool true if the matrix is correct, false otherwise
	 */
	public function check() {
		$zRowsOk = $this->checkRows();
		$zColsOk = $this->checkCols();
		$zSquaresOk = $this->checkSquares();
		return $zRowsOk && $zColsOk && $zSquaresOk;
	}

	/**
	 * Set the value for a cell
	 * @param $iRow Row number
	 * @param $iCol Column number
	 * @param $iValue Value to set
	 *
	 * @return bool true if set value is valid, false otherwise
	 */
	public function setCell($iRow,$iCol,$iValue) {
		$this->aValues[$iRow*9+$iCol] = $iValue;
		return $this->check();
	}

	/**
	 * Removes the value in a cell
	 * @param $iRow Row number
	 * @param $iCol Column number
	 */
	public function unsetCell($iRow,$iCol) {
		$this->aValues[$iRow*9+$iCol] = 0;
		return true;
	}

	/**
	 * Get the matrix values
	 *
	 * @return array Values of the Sudoku Matrix
	 */
	public function getCells(){
		return $this->aValues;
	}

	/**
	 * Check if the matrix is complete
	 *
	 * @return bool true if complete, false otherwise
	 */
	public function complete() {
		return array_sum($this->aValues) == self::SUDOKU_MATRIX_SUM;
	}

	/**
	 * Get an array of valid values for a cell
	 * @param $iRow Row number
	 * @param $iCol Column number
	 *
	 * @return array Array of valid numbers for the cell
	 */
	public function getValidValues($iRow,$iCol) {
		$aValidValues = array();
		$aUsedValues = $this->getUsedNumbers($iRow,$iCol);
		for ($i=1;$i<=9;$i++) {
			if (!in_array($i,$aUsedValues)) {
				$aValidValues[] = $i;
			}
		}
		return $aValidValues;
	}

	/*
	 * Check the rows in the matrix
	 */
	private function checkRows() {
		$zOk = true;
		$i = 0;
		while (($i < 9 ) && $zOk) {
			$zOk = $this->checkRow($i++);
		}
		return $zOk;
	}

	/*
	 * Check the columns in the matrix
	 */
	private function checkCols() {
		$zOk = true;
		$i = 0;
		while (($i < 9 ) && $zOk) {
			$zOk = $this->checkCol($i++);
		}
		return $zOk;
	}

	/*
	 * Check the 3x3 squares in the matrix
	 */
	private function checkSquares() {
		$zOk = true;
		$i = 0;
		while (($i<9) && $zOk) {
			$zOk = $this->checkSquare($i++);
		}
		return $zOk;
	}

	/*
	 * Check a row
	 * @param $iRow Row number (0 is first column)
	 */
	private function checkRow($iRow) {
		$iSum = 0;
		$i=0;
		$zOk = true;
		$aRowValues = array();
		while ($i<9 && $zOk) {
			$zOk = !$this->repeatedValue($this->aValues[$iRow*9+$i],$aRowValues);
			$aRowValues[] = $this->aValues[$iRow*9+$i];
			$i++;
		}
		return $zOk;
	}

	/*
	 * Check a column
	 * @param $iCol Column number (0 is first column)
	 */
	private function checkCol($iCol) {
		$iSum = 0;
		$i=0;
		$zOk = true;
		$aColValues = array();
		while ($i<9 && $zOk) {
			$zOk = !$this->repeatedValue($this->aValues[$i*9+$iCol],$aColValues);
			$aColValues[] = $this->aValues[$i*9+$iCol];
			$i++;
		}
		return $zOk;
	}

	/*
	 * Check a 3x3 square in the matrix
	 * @param $iSquare Square number, begining from top-left (0),
	 * and following from left to right and from top to bottom
	 */
	private function checkSquare($iSquare) {
		$iSum = 0;
		$i=0;
		$zOk = true;
		$aSquareValues = array();
		$iRowOffset = floor($iSquare/3)*3;
		$iColOffset = ($iSquare%3)*3;
		while ($i<3 && $zOk) {
			$j=0;
			while ($j<3 && $zOk) {
				$zOk = !$this->repeatedValue($this->aValues[($iRowOffset+$i)*9+($iColOffset+$j)],$aSquareValues);
				$aSquareValues[] = $this->aValues[($iRowOffset+$i)*9+($iColOffset+$j)];
				$j++;
			}
			$i++;
		}
		return $zOk;
	}

	/*
	 * Set the initial values for the Sudoku Matrix
	 * @param $aInitValues Initial array of values
	 *
	 * @return bool true if init value is ok, false, otherwise
	 */
	private function init($aInitValues) {
		$this->aValues = $aInitValues;
		return $this->check();
	}

	/*
	 * Check if a value is contained in an array of values
	 * @param $iValue Value to check
	 * @param $aValues Array of values to compare
	 */
	private function repeatedValue($iValue,$aValues) {
		$zRepeated = $iValue!=0?in_array($iValue,$aValues):false;
		return $zRepeated;
	}

	/*
	 * Generate the values for the SudokuMatrix
	 */
	private function generateValues() {
		$iRowChanges = rand(0,10);
		$iColChanges = rand(0,10);
		$this->aValues = $this->aSeed;
		$this->reorderRows($iRowChanges);
		$this->reorderCols($iColChanges);
	}

	/*
	 * Reorder rows making a rotation of the rows in the
	 * matrix taking groups of three.
	 *
	 * @param $iNumChanges Number of row rotations
	 */
	private function reorderRows($iNumChanges) {
		for ($iChange=0;$iChange<$iNumChanges;$iChange++) {
			$this->rotateRows(0,1,2);
			$this->rotateRows(3,4,5);
			$this->rotateRows(6,7,8);
		}
	}

	/*
	 * Rotate three rows
	 * @param $iRow1 Row 1 to rotate
	 * @param $iRow2 Row 2 to rotate
	 * @param $iRow3 Row 3 to rotate
	 */
	private function rotateRows($iRow1,$iRow2,$iRow3) {
		for ($iCol=0;$iCol<9;$iCol++) {
			$iTmp = $this->aValues[$iRow3*9+$iCol];
			$this->aValues[$iRow3*9+$iCol] = $this->aValues[$iRow2*9+$iCol];
			$this->aValues[$iRow2*9+$iCol] = $this->aValues[$iRow1*9+$iCol];
			$this->aValues[$iRow1*9+$iCol] = $iTmp;
		}
	}

	/*
	 * Reorder columns making a rotation of the columns in the
	 * matrix taking groups of three.
	 *
	 * @param $iNumChanges Number of column rotations
	 */
	private function reorderCols($iNumChanges) {
		for ($iChange=0;$iChange<$iNumChanges;$iChange++) {
			$this->rotateCols(0,1,2);
			$this->rotateCols(3,4,5);
			$this->rotateCols(6,7,8);
		}
	}

	/*
	 * Rotate three columns
	 * @param $iCol1 Column 1 to rotate
	 * @param $iCol2 Column 2 to rotate
	 * @param $iCol3 Column 3 to rotate
	 */
	private function rotateCols($iCol1,$iCol2,$iCol3) {
		for ($iRow=0;$iRow<9;$iRow++) {
			$iTmp = $this->aValues[$iRow*9+$iCol3];
			$this->aValues[$iRow*9+$iCol3] = $this->aValues[$iRow*9+$iCol2];
			$this->aValues[$iRow*9+$iCol2] = $this->aValues[$iRow*9+$iCol1];
			$this->aValues[$iRow*9+$iCol1] = $iTmp;
		}
	}

	/*
	 * Hide values in the matrix
	 * @param $iLevel Difficult level used to set the number of hidden cells
	 */
	private function hideValues($iLevel) {
		$iMax = $this->aMaxHidden[$iLevel];
		$iNumHidden = 0;
		for ($i=0;$i<81;$i++) {
			if (rand(0,1)!=0 && $iNumHidden<$iMax) {
				$this->aValues[$i] = 0;
				$iNumHidden++;
			}
		}
	}

	/*
	 * Get the used numbers related to a cell
	 */
	private function getUsedNumbers($iRow,$iCol) {
		$aUsedNumbers = array();
		$aUsedRowNumbers = $this->getRowUsedNumbers($iRow);
		$aUsedColumnNumbers = $this->getColumnUsedNumbers($iCol);
		$aUsedSquareNumbers = $this->getSquareUsedNumbers($this->getSquareNumber($iRow,$iCol));
		$aUsedNumbers = array_merge($aUsedRowNumbers,$aUsedColumnNumbers,$aUsedSquareNumbers);
		return $aUsedNumbers;
	}

	/*
	 * Get the used numbers in a row
	 */
	private function getRowUsedNumbers($iRow) {
		$aUsed = array();
		for($i=0;$i<9;$i++) {
			$aValue = $this->aValues[$iRow*9+$i];
			if ($aValue != 0) {
				$aUsed[] = $aValue;
			}
		}
		return $aUsed;
	}

	/*
	 * Get the used numbers in a column
	 */
	private function getColumnUsedNumbers($iCol) {
		$aUsed = array();
		for($i=0;$i<9;$i++) {
			$aValue = $this->aValues[$i*9+$iCol];
			if ($aValue != 0) {
				$aUsed[] = $aValue;
			}
		}
		return $aUsed;
	}

	/*
	 * Calculate the square number related to a cell
	 */
	private function getSquareNumber($iRow,$iCol) {
		if ($iRow < 3) {
			$iNum = $iCol<3?0:($iCol<6?1:2);
		} elseif ($iRow < 6) {
			$iNum = $iCol<3?3:($iCol<6?4:5);
		} else {
			$iNum = $iCol<3?6:($iCol<6?7:8);
		}
		return $iNum;
	}

	/*
	 * Get the used numbers in a square
	 */
	private function getSquareUsedNumbers($iSquare) {
		$aUsed = array();
		$iRowOffset = floor($iSquare/3)*3;
		$iColOffset = ($iSquare%3)*3;
		for($i=0;$i<3;$i++) {
			for($j=0;$j<3;$j++) {
				$aValue = $this->aValues[($iRowOffset+$i)*9+($iColOffset+$j)];
				if ($aValue != 0) {
					$aUsed[] = $aValue;
				}
			}
		}
		return $aUsed;
	}
}
?>
